/**
 DP, （通过leetcode该题的测试用例约112ms，待优化）
 * @param {number} target
 * @param {number} startFuel
 * @param {number[][]} stations
 * @return {number}
 */
export var minRefuelStops = function (target, startFuel, stations) {
  if (startFuel >= target) return 0
  // dp[i][j] 表示到达第i个站时,一共加过j次油后的最多乘余油量（能续行的公里数），
  // i 从 0 开始，0表示出发点，
  const n = stations.length
  const dp = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(-Infinity))

  // 出发点未加油有startFuel的油里
  dp[0][0] = startFuel
  let i = 1
  let sGone = 0 // 已走路程
  let ans = Infinity
  out: while (i <= n) {
    const [s, fuel] = stations[i - 1]
    const sDiff = s - sGone // 上一站到此站的距离
    sGone = s
    // 是否能到达本站
    let isCanReachCurr = false
    if (sGone >= target) return ans
    for (let j = 0; j <= n; j++) {
      // 每次都检查是否能到达当前站 (上一轮的余油量 >= sDiff)
      // console.log([i, j], `s=${s}`, `dp[i - 1][j]=${dp[i - 1][j]}`, 'sDiff = ${sDiff}', dp[i - 1][j] >= sDiff, ans)
      if (dp[i - 1][j] >= sDiff || sGone >= target) isCanReachCurr = true
      // 到到第i站(已加j次油)当前站未加油时的最大乘油量
      const suprplusFuel0 = dp[i - 1][j] - sDiff < 0 ? -Infinity : dp[i - 1][j] - sDiff
      // 到到第i站(已加j - 1次油)当前站未加油时的最大乘油量
      const suprplusFuel1 =
        j === 0 || dp[i - 1][j - 1] - sDiff < 0 ? -Infinity : dp[i - 1][j - 1] - sDiff
      // 本次不加油和本次加油的最大乘油量
      dp[i][j] = Math.max(suprplusFuel0, suprplusFuel1 + fuel)
      if (sGone + dp[i][j] >= target && isCanReachCurr) {
        if (j < ans) ans = j
        if (ans !== Infinity) {
          i++
          continue out
        }
      }
    }
    if (!isCanReachCurr) return -1
    i++
  }
  // console.log('dp', dp)
  return ans === Infinity ? -1 : ans
}

/**
 一维DP（动态规划似乎都不快）
 * @param {number} target
 * @param {number} startFuel
 * @param {number[][]} stations
 * @return {number}
 */
export var minRefuelStops2 = function (target, startFuel, stations) {
  if (startFuel >= target) return 0
  const n = stations.length
  // const dp = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(-Infinity))
  let dp = new Array(n + 1).fill(-Infinity)

  // 出发点未加油有startFuel的油里
  dp[0] = startFuel
  let sGone = 0 // 已走路程
  let ans = Infinity
  for (let i = 0; i < n; i++) {
    const [s, fuel] = stations[i]
    const sDiff = s - sGone // 上一站到此站的距离
    sGone = s
    // 是否能到达本站
    let isCanReachCurr = false
    if (s >= target) return ans
    const newDp = new Array(n + 1).fill(-Infinity)
    for (let j = 0; j <= n; j++) {
      // 每次都检查是否能到达当前站 (上一轮的余油量 >= sDiff)
      if (dp[j] >= sDiff) isCanReachCurr = true
      // 到第i站(已加j次油)当前站未加油时的最大乘油量
      const suprplusFuel0 = dp[j] - sDiff < 0 ? -Infinity : dp[j] - sDiff
      // 到第i站(已加j - 1次油)当前站未加油时的最大乘油量
      const suprplusFuel1 = j === 0 || dp[j - 1] - sDiff < 0 ? -Infinity : dp[j - 1] - sDiff
      // 本次不加油和本次加油的最大乘油量
      newDp[j] = Math.max(suprplusFuel0, suprplusFuel1 + fuel)
      if (s + newDp[j] >= target && isCanReachCurr && j < ans) ans = j
    }
    dp = newDp
    if (!isCanReachCurr) return -1
  }
  // console.log('dp', dp)
  return ans === Infinity ? -1 : ans
}

// 小顶堆方法leetcode官方有提供
import MinPriorityQueue from '../../helper/MinPriorityQueue'

/**
大顶堆
 * @param {number} target
 * @param {number} startFuel
 * @param {number[][]} stations
 * @return {number}
 */
export var minRefuelStops3 = function (target, startFuel, stations) {
  let canGo = startFuel // 当前可走到的最远路程
  const heapQ = new MinPriorityQueue() // 使用最小优先队列
  let ans = 0
  stations.push([target, 0])

  for (let i = 0; i < stations.length; i++) {
    const [s, fuel] = stations[i]
    while (canGo < s) {
      if (heapQ.isEmpty()) return -1
      const addFuel = heapQ.dequeue()
      canGo += addFuel.element
      ans++
    }
    heapQ.enqueue(fuel, -fuel)
  }
  return ans
}
